package com.leetcode.根据算法进行分类.双指针相关;

import java.util.Comparator;
import java.util.HashSet;
import java.util.PriorityQueue;

/**
 * @author: ZhouBert
 * @date: 2021/2/4
 * @description: 11. 盛最多水的容器
 * https://leetcode-cn.com/problems/container-with-most-water/
 * 此题是 {@link C_42_接雨水} 的简单版本
 * 将竖线看成不占面积的薄板即可。
 * 一般需要移动左右两头的问题，可以考虑双指针！
 */
public class B_11_盛最多水的容器 {

	public static void main(String[] args) {
		int[] height = new int[]{1, 8, 6, 2, 5, 4, 8, 3, 7};
		B_11_盛最多水的容器 action = new B_11_盛最多水的容器();
		int res = action.maxAreaByTwoPoint(height);
		System.out.println("res = " + res);
	}


	/**
	 * 终于看懂了双指针的解法。
	 * 反思一下：
	 * 1.这种【最值问题】，理应不会用暴力解法去计算所有的解；而是应该仔细琢磨变化的趋势，
	 * 以省略没有必要的计算；
	 * 2.最大宽度是可以直接得到的，此时如果要想让面积增大，只能缩小宽度的同时增大长度！
	 * 那么可以使用双指针，每次移动最短的边，直至结束。
	 * --
	 * 双指针确实是个好办法！
	 * @param height
	 * @return
	 */
	public int maxAreaByTwoPoint(int[] height) {
		int len = height.length;
		int res = 0;
		if (len < 2) {
			return res;
		}
		int left = 0, right = len - 1;
		while (left < right) {
			if (height[left] < height[right]) {
				//如果 left 较短
				res = Math.max(res, height[left] * (right - left));
				left++;
			} else {
				res = Math.max(res, height[right] * (right - left));
				right--;
			}
		}

		return res;
	}


	/**
	 * 根据短板原理
	 * 本题似乎不能用动态规划，因为木有找到状态转移。
	 * --
	 * 一种是暴力解法，将所有的情况都算一遍：O(n^2)
	 * or 按照宽度从大到小进行筛选，同样需要 O(n^2)
	 * --
	 * 上面肯定是很低效的，那么：
	 * 1.遍历一遍，通过 小顶堆进行排序；（由于短板效应，这样简化了问题，每一次只需要判断最大的宽度即可）
	 * 2.将已经排序过的 index 放入 set,还需要维护左右边界即可。
	 * --
	 * 我承认我想不到双指针！
	 * 居然可以O(n) 得解。
	 * 必须要好好学习下
	 *
	 * @param height
	 * @return
	 */
	public int maxAreaByHeap(int[] height) {
		int len = height.length;
		int res = 0;
		if (len < 2) {
			return res;
		}
		PriorityQueue<Board> heap = new PriorityQueue<>(new Comparator<Board>() {
			@Override
			public int compare(Board o1, Board o2) {
				return o1.value - o2.value;
			}
		});
		for (int i = 0; i < len; i++) {
			heap.offer(new Board(i, height[i]));
		}
		Board minBoard;
		//维护的边界
		int begin = 0, end = len - 1;
		int index = 0;
		HashSet<Integer> visitedIndexSet = new HashSet<>();
		while (heap.size() > 1) {
			minBoard = heap.poll();
			index = minBoard.index;
			if (index == begin) {
				while (visitedIndexSet.contains(++begin)) {
				}

				res = Math.max(res, (end - index) * minBoard.value);
			} else if (index == end) {
				while (visitedIndexSet.contains(--end)) {
				}

				res = Math.max(res, (index - begin) * minBoard.value);
			} else {
				visitedIndexSet.add(index);
				res = Math.max(res, Math.max(end - index, index - begin) * minBoard.value);
			}
		}
		return res;

	}

	/**
	 * 板
	 */
	static class Board {
		int index;
		int value;

		public Board(int index, int value) {
			this.index = index;
			this.value = value;
		}
	}

}
